/*
实验2-1 求链式线性表的倒数第 m 项
分数 20
作者 陈越
单位 浙江大学

请设计时间和空间上都尽可能高效的算法，求链式存储的线性表的倒数第m（>0）个元素。
函数接口定义：

ElemSet Find( List list, int m );

其中List结构定义如下：

typedef struct ListNode *Position; /* 指针即结点位置
typedef Position List;
struct ListNode {
    ElemSet data;  /* 存储数据
    Position next;  /* 线性表中下一个元素的位置
};

函数接口定义中，ElemSet 是用户定义的数据类型，例如 int、double 或者 char 等。
函数 Find 的功能是，返回带空头结点的单链表 list 的倒数第 m 个元素的值，
并且不得对 list 做任何改变。如果这样的元素不存在，则返回一个错误标志
ERROR（这个标志的值由裁判程序定义）。

输入样例：

5
1 2 4 5 6
3

输出样例：

4
1 2 4 5 6
*/

#include <stdio.h>
#include <stdlib.h>

#define ERROR -1
typedef int ElemSet;
typedef struct ListNode *Position; /* 指针即结点位置 */
typedef Position List;
struct ListNode {
    ElemSet data;  /* 存储数据 */
    Position next; /* 线性表中下一个元素的位置 */
};

List ReadList() { /* 创建带空头结点的、有n个数据结点的单链表 */
    List p, rear;
    int n;
    scanf("%d", &n);
    p = (List)malloc(sizeof(struct ListNode));
    p->next = NULL;
    rear = p;
    while (n--) { /* 新读入的数据插在链表尾 */
        rear->next = (List)malloc(sizeof(struct ListNode));
        scanf("%d", &rear->next->data);
        rear->next->next = NULL;
        rear = rear->next;
    }
    return p;
}

void PrintList(List list) { /* 顺序输出带空头结点的单链表的结点数据 */
    while (list->next != NULL) {
        list = list->next;
        printf("%d ", list->data);
    }
    printf("\n");
}

ElemSet Find(List list, int m);

int main(void) {
    List list;
    int m;

    list = ReadList();
    scanf("%d", &m);
    printf("%d\n", Find(list, m));
    PrintList(list);
    return 0;
}
/* 你的代码将被嵌在这里 */

ElemSet Find(List list, int m) {
    Position rear = list->next;
    while (m--) {
        if (rear == NULL) {
            return ERROR;
        }
        rear = rear->next;
    }
    Position front = list->next;
    while (rear != NULL) {
        rear = rear->next;
        front = front->next;
    }
    return front->data;
}